<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 6.0.0">
  <link rel="apple-touch-icon" sizes="180x180" href="/wang-cheng/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/wang-cheng/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/wang-cheng/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/wang-cheng/images/logo.svg" color="#222">

<link rel="stylesheet" href="/wang-cheng/css/main.css">


<link rel="stylesheet" href="/wang-cheng/lib/font-awesome/css/all.min.css">

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"cheng-wang123.gitee.io","root":"/wang-cheng/","scheme":"Gemini","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":false,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}}};
  </script>

  <meta name="description" content="ConcurrentHashMap源码分析ConcurrentHashMap在1.7的时候，new ConcurrentHashMap(32)的时候，此时数组长度就是32。但是在1.8之后，new ConcurrentHashMap(32)就不再是32，而是64。 因为ConcurrentHashMap和HashMap一样，是因为他要保证它的初始值是2的幂次方，这样可以使得添加的元素均匀分布在Ha">
<meta property="og:type" content="article">
<meta property="og:title" content="ConcurrentHashMap源码专题">
<meta property="og:url" content="https://cheng-wang123.gitee.io/wang-cheng/2022/04/29/ConcurrentHashMap%E6%BA%90%E7%A0%81%E4%B8%93%E9%A2%98/index.html">
<meta property="og:site_name" content="诚の博客">
<meta property="og:description" content="ConcurrentHashMap源码分析ConcurrentHashMap在1.7的时候，new ConcurrentHashMap(32)的时候，此时数组长度就是32。但是在1.8之后，new ConcurrentHashMap(32)就不再是32，而是64。 因为ConcurrentHashMap和HashMap一样，是因为他要保证它的初始值是2的幂次方，这样可以使得添加的元素均匀分布在Ha">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2022-04-29T01:26:20.000Z">
<meta property="article:modified_time" content="2022-05-01T04:38:07.629Z">
<meta property="article:author" content="王诚">
<meta property="article:tag" content="源码分析">
<meta name="twitter:card" content="summary">

<link rel="canonical" href="https://cheng-wang123.gitee.io/wang-cheng/2022/04/29/ConcurrentHashMap%E6%BA%90%E7%A0%81%E4%B8%93%E9%A2%98/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>ConcurrentHashMap源码专题 | 诚の博客</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

<link rel="alternate" href="/wang-cheng/atom.xml" title="诚の博客" type="application/atom+xml">
</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/wang-cheng/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">诚の博客</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
      <p class="site-subtitle" itemprop="description">记录学习中的点点滴滴</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-home">

    <a href="/wang-cheng/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/wang-cheng/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/wang-cheng/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/wang-cheng/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a>

  </li>
  </ul>
</nav>




</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://cheng-wang123.gitee.io/wang-cheng/2022/04/29/ConcurrentHashMap%E6%BA%90%E7%A0%81%E4%B8%93%E9%A2%98/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/wang-cheng/images/avatar.gif">
      <meta itemprop="name" content="王诚">
      <meta itemprop="description" content="命运对勇士低语，你无法抵御风暴；勇士低声回应，我就是风暴">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="诚の博客">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          ConcurrentHashMap源码专题
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              <time title="创建时间：2022-04-29 09:26:20" itemprop="dateCreated datePublished" datetime="2022-04-29T09:26:20+08:00">2022-04-29</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2022-05-01 12:38:07" itemprop="dateModified" datetime="2022-05-01T12:38:07+08:00">2022-05-01</time>
              </span>

          
            <span class="post-meta-item" title="阅读次数" id="busuanzi_container_page_pv" style="display: none;">
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              <span class="post-meta-item-text">阅读次数：</span>
              <span id="busuanzi_value_page_pv"></span>
            </span>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <h1 id="ConcurrentHashMap源码分析"><a href="#ConcurrentHashMap源码分析" class="headerlink" title="ConcurrentHashMap源码分析"></a><strong>ConcurrentHashMap源码分析</strong></h1><p>ConcurrentHashMap在1.7的时候，new ConcurrentHashMap(32)的时候，此时数组长度就是32。但是在1.8之后，new ConcurrentHashMap(32)就不再是32，而是64。</p>
<p>因为ConcurrentHashMap和HashMap一样，是因为他要保证它的初始值是2的幂次方，这样可以使得添加的元素均匀分布在HashMap中的数组上，减少hash碰撞。</p>
<h2 id="ConcurrentHashMap初始化-CAS加自旋"><a href="#ConcurrentHashMap初始化-CAS加自旋" class="headerlink" title="ConcurrentHashMap初始化 CAS加自旋"></a><strong>ConcurrentHashMap初始化</strong> CAS加自旋</h2><p>ConcurrentHashMap的初始化操作(ConcurrentHashMap没用锁，提高了效率)</p>
<figure class="highlight stata"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line">private final Node&lt;K,V&gt;[] initTable()&#123;</span><br><span class="line">    Node&lt;K,V&gt;[] <span class="keyword">tab</span>; int <span class="keyword">sc</span>;</span><br><span class="line">    <span class="keyword">while</span>((<span class="keyword">tab</span> = <span class="keyword">table</span>) == null || <span class="keyword">tab</span>.length == 0)&#123;</span><br><span class="line">        <span class="keyword">if</span>((<span class="keyword">sc</span>=sizeCtl) &lt; 0)&#123;</span><br><span class="line">            Thread.yield();</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(<span class="keyword">U</span>.comparaeAndSwapInt(this,SIZECTL,<span class="keyword">sc</span>,-1))&#123;</span><br><span class="line">            try&#123;</span><br><span class="line">                <span class="keyword">if</span>((<span class="keyword">tab</span>=<span class="keyword">table</span>) == null || <span class="keyword">tab</span>.length==0)&#123;</span><br><span class="line">                    int <span class="keyword">n</span> = (<span class="keyword">sc</span>&gt;0)?<span class="keyword">sc</span>:DEFAULT_CAPACITY;</span><br><span class="line">                    @SuppressWarning(<span class="string">&quot;unchecked&quot;</span>)</span><br><span class="line">                    Node&lt;K,V&gt;[] nt = (Nde&lt;K,V&gt;[])new Node&lt;?,?&gt;[<span class="keyword">n</span>];</span><br><span class="line">                    <span class="keyword">table</span> = <span class="keyword">tab</span> = nt;</span><br><span class="line">                    <span class="keyword">sc</span> = <span class="keyword">n</span> - (<span class="keyword">n</span> &gt;&gt;&gt; 2);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;finally&#123;</span><br><span class="line">                sizeCtl = <span class="keyword">sc</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">tab</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>其中sizeCtl是成员变量，该变量为0时表示还未进行初始化，此时容器默认容量为16。当该变量为正数时表示为该容器设置了大小。当该变量为-1时，表示容器正在进行初始化。当该变量为负数时，表示容器正在进行扩容。</p>
<p>在initTable方法中，首先会判断sizeCtl的值，如果小于0，证明其他线程正在进行扩容或初始化，此时该线程会让出cpu。</p>
<p>如果sizeCtl大于0，则进行容器的初始化。这里使用了CAS操作，在不使用sychronized锁的情况下进行初始化。初始化完成后，将sizeCtl记录的就变成了扩容阈值(触发扩容的临界条件)</p>
<h2 id="ConcurrentHashMap的存值操作-CAS加自旋"><a href="#ConcurrentHashMap的存值操作-CAS加自旋" class="headerlink" title="ConcurrentHashMap的存值操作 CAS加自旋"></a><strong>ConcurrentHashMap的存值操作</strong> CAS加自旋</h2><p>ConcurrentHashMap的put方法<br><figure class="highlight arcade"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//put操作</span></span><br><span class="line">public V put(K key, V value) &#123;</span><br><span class="line">    <span class="keyword">return</span> putVal(key, value, <span class="literal">false</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">final V putVal(K key, V value, <span class="built_in">boolean</span> onlyIfAbsent) &#123;</span><br><span class="line">    <span class="keyword">if</span> (key == <span class="literal">null</span> || value == <span class="literal">null</span>) throw <span class="keyword">new</span> NullPointerException();<span class="comment">//不允许为null</span></span><br><span class="line">    int <span class="built_in">hash</span> = spread(key.hashCode());</span><br><span class="line">    int binCount = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (Node&lt;K,V&gt;[] <span class="literal">tab</span> = table;;) &#123;</span><br><span class="line">        Node&lt;K,V&gt; f; int n, i, fh;</span><br><span class="line">        <span class="keyword">if</span> (<span class="literal">tab</span> == <span class="literal">null</span> || (n = <span class="literal">tab</span>.<span class="built_in">length</span>) == <span class="number">0</span>)</span><br><span class="line">            <span class="literal">tab</span> = initTable();</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> ((f = tabAt(<span class="literal">tab</span>, i = (n - <span class="number">1</span>) &amp; <span class="built_in">hash</span>)) == <span class="literal">null</span>) &#123;<span class="comment">//tabAt利用hash去取数组中这个下标对应的值，取值的操作是一个CAS操作，且保证可见性</span></span><br><span class="line">            <span class="keyword">if</span> (casTabAt(<span class="literal">tab</span>, i, <span class="literal">null</span>,</span><br><span class="line">                            <span class="keyword">new</span> Node&lt;K,V&gt;(<span class="built_in">hash</span>, key, value, <span class="literal">null</span>)))</span><br><span class="line">                <span class="keyword">break</span>;                   <span class="comment">// no lock when adding to empty bin</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> ((fh = f.<span class="built_in">hash</span>) == MOVED)</span><br><span class="line">            <span class="literal">tab</span> = helpTransfer(<span class="literal">tab</span>, f);</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            V oldVal = <span class="literal">null</span>;</span><br><span class="line">            synchronized (f) &#123;<span class="comment">//这里的f是算出来的hash值所在的数组的链的头节点。</span></span><br><span class="line">                <span class="keyword">if</span> (tabAt(<span class="literal">tab</span>, i) == f) &#123;</span><br><span class="line">                    <span class="keyword">if</span> (fh &gt;= <span class="number">0</span>) &#123;<span class="comment">//fh大于0证明是一个链表</span></span><br><span class="line">                        binCount = <span class="number">1</span>;</span><br><span class="line">                        <span class="keyword">for</span> (Node&lt;K,V&gt; e = f;; ++binCount) &#123;<span class="comment">//找到数组对应的下标后，依次遍历链表</span></span><br><span class="line">                            K ek;</span><br><span class="line">                            <span class="keyword">if</span> (e.<span class="built_in">hash</span> == <span class="built_in">hash</span> &amp;&amp;</span><br><span class="line">                                ((ek = e.key) == key ||</span><br><span class="line">                                    (ek != <span class="literal">null</span> &amp;&amp; key.<span class="built_in">equals</span>(ek)))) &#123;</span><br><span class="line">                                oldVal = e.val;</span><br><span class="line">                                <span class="keyword">if</span> (!onlyIfAbsent)</span><br><span class="line">                                    e.val = value;</span><br><span class="line">                                <span class="keyword">break</span>;</span><br><span class="line">                            &#125;</span><br><span class="line">                            Node&lt;K,V&gt; pred = e;</span><br><span class="line">                            <span class="keyword">if</span> ((e = e.next) == <span class="literal">null</span>) &#123;</span><br><span class="line">                                pred.next = <span class="keyword">new</span> Node&lt;K,V&gt;(<span class="built_in">hash</span>, key,</span><br><span class="line">                                                            value, <span class="literal">null</span>);</span><br><span class="line">                                <span class="keyword">break</span>;</span><br><span class="line">                            &#125;</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125;</span><br><span class="line">                    <span class="keyword">else</span> <span class="keyword">if</span> (f instanceof TreeBin) &#123;<span class="comment">//证明是一棵二叉树</span></span><br><span class="line">                        Node&lt;K,V&gt; p;</span><br><span class="line">                        binCount = <span class="number">2</span>;</span><br><span class="line">                        <span class="keyword">if</span> ((p = ((TreeBin&lt;K,V&gt;)f).putTreeVal(<span class="built_in">hash</span>, key,</span><br><span class="line">                                                        value)) != <span class="literal">null</span>) &#123;</span><br><span class="line">                            oldVal = p.val;</span><br><span class="line">                            <span class="keyword">if</span> (!onlyIfAbsent)</span><br><span class="line">                                p.val = value;</span><br><span class="line">                        &#125;</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (binCount != <span class="number">0</span>) &#123;</span><br><span class="line">                <span class="keyword">if</span> (binCount &gt;= TREEIFY_THRESHOLD)<span class="comment">//判断链表长度是否大于8，大于8的话再判断数组长度是否大于64。如果都满足，则将链表变为红黑树。如果链表长度大于8，数组长度不大于64，则先进行扩容。</span></span><br><span class="line">                    treeifyBin(<span class="literal">tab</span>, i);</span><br><span class="line">                <span class="keyword">if</span> (oldVal != <span class="literal">null</span>)</span><br><span class="line">                    <span class="keyword">return</span> oldVal;</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    addCount(<span class="number">1</span>L, binCount);</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>synchronized (f)：锁住的是头节点，当多个线程添加元素，算出来的hash值都是一个数组所对应的下标时，通过锁机制，利用sychronized锁让线程按顺序执行，保证了线程安全。同时，当多个线程同时进行添加操作，但多个线程添加的元素的hash值并不是同一个hash值时，多个线程添加元素将不会收到影响，同时也不会对线程安全产生影响，提高了添加元素的效率。</p>
<p>在放入元素最后，调用了addCount方法，来计算和维护这个集合的长度。</p>
<h2 id="如何计算-ConcurrentHashMap-Size"><a href="#如何计算-ConcurrentHashMap-Size" class="headerlink" title="如何计算 ConcurrentHashMap Size"></a><strong>如何计算 ConcurrentHashMap Size</strong></h2><p>在实际的项目过程中，我们通常需要获取集合类的长度， 那么计算 ConcurrentHashMap 的元素大小就是一个有趣的问题，因为他是并发操作的，就是在你计算 size 的时候，它还在并发的插入数据，可能会导致你计算出来的 size 和你实际的 size 有差距。本文主要分析下 JDK1.8 的实现。 关于 JDK1.7 简单提一下。</p>
<p>在 JDK1.7 中，第一种方案他会使用不加锁的模式去尝试多次计算 ConcurrentHashMap 的 size，最多三次，比较前后两次计算的结果，结果一致就认为当前没有元素加入，计算的结果是准确的。 第二种方案是如果第一种方案不符合，他就会给每个 Segment 加上锁，然后计算 ConcurrentHashMap 的 size 返回。其源码实现:</p>
<figure class="highlight arduino"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="type">int</span> <span class="title">size</span><span class="params">()</span> </span>&#123;</span><br><span class="line">  <span class="keyword">final</span> Segment&lt;K,V&gt;[] segments = <span class="keyword">this</span>.segments;</span><br><span class="line">  <span class="type">int</span> size;</span><br><span class="line">  <span class="type">boolean</span> overflow; <span class="comment">// true if size overflows 32 bits</span></span><br><span class="line">  <span class="type">long</span> sum;         <span class="comment">// sum of modCounts</span></span><br><span class="line">  <span class="type">long</span> last = <span class="number">0L</span>;   <span class="comment">// previous sum</span></span><br><span class="line">  <span class="type">int</span> retries = <span class="number">-1</span>; <span class="comment">// first iteration isn&#x27;t retry</span></span><br><span class="line">  <span class="keyword">try</span> &#123;</span><br><span class="line">    <span class="keyword">for</span> (;;) &#123;</span><br><span class="line">      <span class="keyword">if</span> (retries++ == RETRIES_BEFORE_LOCK) &#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; segments.length; ++j)</span><br><span class="line">          <span class="built_in">ensureSegment</span>(j).<span class="built_in">lock</span>(); <span class="comment">// force creation</span></span><br><span class="line">      &#125;</span><br><span class="line">      sum = <span class="number">0L</span>;</span><br><span class="line">      size = <span class="number">0</span>;</span><br><span class="line">      overflow = <span class="literal">false</span>;</span><br><span class="line">      <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; segments.length; ++j) &#123;</span><br><span class="line">        Segment&lt;K,V&gt; seg = <span class="built_in">segmentAt</span>(segments, j);</span><br><span class="line">        <span class="keyword">if</span> (seg != null) &#123;</span><br><span class="line">          sum += seg.modCount;</span><br><span class="line">          <span class="type">int</span> c = seg.count;</span><br><span class="line">          <span class="keyword">if</span> (c &lt; <span class="number">0</span> || (size += c) &lt; <span class="number">0</span>)</span><br><span class="line">            overflow = <span class="literal">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line">      &#125;</span><br><span class="line">      <span class="keyword">if</span> (sum == last)</span><br><span class="line">        <span class="keyword">break</span>;</span><br><span class="line">      last = sum;</span><br><span class="line">    &#125;</span><br><span class="line">  &#125; finally &#123;</span><br><span class="line">    <span class="keyword">if</span> (retries &gt; RETRIES_BEFORE_LOCK) &#123;</span><br><span class="line">      <span class="keyword">for</span> (<span class="type">int</span> j = <span class="number">0</span>; j &lt; segments.length; ++j)</span><br><span class="line">        <span class="built_in">segmentAt</span>(segments, j).<span class="built_in">unlock</span>();</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">return</span> overflow ? Integer.MAX_VALUE : size;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>JDK1.8 实现相比 JDK 1.7 简单很多，只有一种方案，我们直接看 size() 代码：</p>
<figure class="highlight csharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="built_in">int</span> <span class="title">size</span>()</span> &#123;</span><br><span class="line">    <span class="built_in">long</span> n = sumCount();</span><br><span class="line">    <span class="keyword">return</span> ((n &lt; <span class="number">0L</span>) ? <span class="number">0</span> :</span><br><span class="line">           (n &gt; (<span class="built_in">long</span>)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (<span class="built_in">int</span>)n);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>最大值是 Integer 类型的最大值，但是 Map 的 size 可能超过 MAX_VALUE， 所以还有一个方法 <code>mappingCount()</code>，JDK 的建议使用 <code>mappingCount()</code> 而不是<code>size()</code>。<code>mappingCount()</code> 的代码如下：</p>
<figure class="highlight csharp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="built_in">long</span> <span class="title">mappingCount</span>()</span> &#123;</span><br><span class="line">    <span class="built_in">long</span> n = sumCount();</span><br><span class="line">    <span class="keyword">return</span> (n &lt; <span class="number">0L</span>) ? <span class="number">0L</span> : n; <span class="comment">// ignore transient negative values</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>以上可以看出，无论是 <code>size()</code> 还是 <code>mappingCount()</code>, 计算大小的核心方法都是 <code>sumCount()</code>。<code>sumCount()</code> 的代码如下:</p>
<figure class="highlight axapta"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">final</span> <span class="built_in">long</span> sumCount() &#123;</span><br><span class="line">    CounterCell[] <span class="keyword">as</span> = counterCells; </span><br><span class="line">    CounterCell a;</span><br><span class="line">    <span class="built_in">long</span> <span class="keyword">sum</span> = baseCount;</span><br><span class="line">    <span class="keyword">if</span> (<span class="keyword">as</span> != <span class="literal">null</span>) &#123;</span><br><span class="line">       <span class="keyword">for</span> (<span class="built_in">int</span> i = <span class="number">0</span>; i &lt; <span class="keyword">as</span>.length; ++i) &#123;</span><br><span class="line">           <span class="keyword">if</span> ((a = <span class="keyword">as</span>[i]) != <span class="literal">null</span>)</span><br><span class="line">               <span class="keyword">sum</span> += a.value;</span><br><span class="line">           &#125;</span><br><span class="line">       &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">sum</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>分析一下<code>sumCount()</code>代码。ConcurrentHashMap 提供了 baseCount、counterCells 两个辅助变量和一个 CounterCell 辅助内部类。<code>sumCount()</code> 就是迭代 counterCells 来统计 sum 的过程。 put 操作时，肯定会影响 <code>size()</code>，在 <code>put()</code> 方法最后会调用 <code>addCount()</code> 方法。</p>
<p><code>addCount</code>方法中的<code>baseCount</code>和<code>counterCells</code>的和是该集合的长度</p>
<p>addCount() 代码如下：</p>
<p>如果 counterCells == null, 则对 baseCount 做 CAS 自增操作。<br><figure class="highlight axapta"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">void</span> addCount(<span class="built_in">long</span> x, <span class="built_in">int</span> check) &#123;</span><br><span class="line">    CounterCell[] <span class="keyword">as</span>; <span class="built_in">long</span> b, s;</span><br><span class="line">    <span class="keyword">if</span> ((<span class="keyword">as</span> = counterCells) != <span class="literal">null</span> ||</span><br><span class="line">        !U.compareAndSwapLong(<span class="keyword">this</span>, BASECOUNT, b = baseCount, s = b + x)) &#123;</span><br><span class="line">        CounterCell a; <span class="built_in">long</span> v; <span class="built_in">int</span> m;</span><br><span class="line">        <span class="built_in">boolean</span> uncontended = <span class="literal">true</span>;</span><br><span class="line">        <span class="keyword">if</span> (<span class="keyword">as</span> == <span class="literal">null</span> || (m = <span class="keyword">as</span>.length - <span class="number">1</span>) &lt; <span class="number">0</span> ||</span><br><span class="line">            (a = <span class="keyword">as</span>[ThreadLocalRandom.getProbe() &amp; m]) == <span class="literal">null</span> ||</span><br><span class="line">            !(uncontended =</span><br><span class="line">                U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) &#123;</span><br><span class="line">            fullAddCount(x, uncontended);</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (check &lt;= <span class="number">1</span>)</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        s = sumCount();</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span> (check &gt;= <span class="number">0</span>) &#123;</span><br><span class="line">        Node&lt;K,V&gt;[] tab, nt; <span class="built_in">int</span> n, sc;</span><br><span class="line">        <span class="keyword">while</span> (s &gt;= (<span class="built_in">long</span>)(sc = sizeCtl) &amp;&amp; (tab = table) != <span class="literal">null</span> &amp;&amp;</span><br><span class="line">                (n = tab.length) &lt; MAXIMUM_CAPACITY) &#123;</span><br><span class="line">            <span class="built_in">int</span> rs = resizeStamp(n);</span><br><span class="line">            <span class="keyword">if</span> (sc &lt; <span class="number">0</span>) &#123;</span><br><span class="line">                <span class="keyword">if</span> ((sc &gt;&gt;&gt; RESIZE_STAMP_SHIFT) != rs || sc == rs + <span class="number">1</span> ||</span><br><span class="line">                    sc == rs + MAX_RESIZERS || (nt = nextTable) == <span class="literal">null</span> ||</span><br><span class="line">                    transferIndex &lt;= <span class="number">0</span>)</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                <span class="keyword">if</span> (U.compareAndSwapInt(<span class="keyword">this</span>, SIZECTL, sc, sc + <span class="number">1</span>))</span><br><span class="line">                    transfer(tab, nt);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span> <span class="keyword">if</span> (U.compareAndSwapInt(<span class="keyword">this</span>, SIZECTL, sc,</span><br><span class="line">                                            (rs &lt;&lt; RESIZE_STAMP_SHIFT) + <span class="number">2</span>))</span><br><span class="line">                transfer(tab, <span class="literal">null</span>);</span><br><span class="line">            s = sumCount();</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>当多个线程添加完元素都来访问<code>baseCount</code>，此时进行CAS操作</p>
<figure class="highlight reasonml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> ((<span class="keyword">as</span> = counterCells) != null<span class="operator"> ||</span></span><br><span class="line"><span class="operator">        </span>!<span class="module-access"><span class="module"><span class="identifier">U</span>.</span></span>compare<span class="constructor">AndSwapLong(<span class="params">this</span>, BASECOUNT, <span class="params">b</span> = <span class="params">baseCount</span>, <span class="params">s</span> = <span class="params">b</span> + <span class="params">x</span>)</span>)</span><br></pre></td></tr></table></figure>
<p>当这个函数是第一次被执行的时候,<code>counterCells</code>默认是null，此时会执行if里面的语句，if里面的语句会对<code>counterCells</code>数组进行创建，并进行初始化。</p>
<p>当这个函数不是第一次被执行的时候，执行CAS操作，CAS操作会对<code>baseCount</code>进行+1操作，当多个线程同时访问<code>baseCount</code>时，只会有一个操作成功，其他线程会进入if里面的语句，对<code>counterCells</code>数组中的某个下标的值进行加1操作。</p>

    </div>

    
    
    

      <footer class="post-footer">
          <div class="post-tags">
              <a href="/wang-cheng/tags/%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/" rel="tag"># 源码分析</a>
          </div>

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/wang-cheng/2022/04/28/%E5%A4%9A%E7%BA%BF%E7%A8%8B%E9%9D%A2%E8%AF%95%E9%A2%98/" rel="prev" title="多线程面试题">
      <i class="fa fa-chevron-left"></i> 多线程面试题
    </a></div>
      <div class="post-nav-item">
    <a href="/wang-cheng/2022/05/05/synchronized%E7%AD%89%E9%94%81%E6%9C%BA%E5%88%B6/" rel="next" title="synchronized等锁机制">
      synchronized等锁机制 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#ConcurrentHashMap%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90"><span class="nav-number">1.</span> <span class="nav-text">ConcurrentHashMap源码分析</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#ConcurrentHashMap%E5%88%9D%E5%A7%8B%E5%8C%96-CAS%E5%8A%A0%E8%87%AA%E6%97%8B"><span class="nav-number">1.1.</span> <span class="nav-text">ConcurrentHashMap初始化 CAS加自旋</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#ConcurrentHashMap%E7%9A%84%E5%AD%98%E5%80%BC%E6%93%8D%E4%BD%9C-CAS%E5%8A%A0%E8%87%AA%E6%97%8B"><span class="nav-number">1.2.</span> <span class="nav-text">ConcurrentHashMap的存值操作 CAS加自旋</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E5%A6%82%E4%BD%95%E8%AE%A1%E7%AE%97-ConcurrentHashMap-Size"><span class="nav-number">1.3.</span> <span class="nav-text">如何计算 ConcurrentHashMap Size</span></a></li></ol></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">王诚</p>
  <div class="site-description" itemprop="description">命运对勇士低语，你无法抵御风暴；勇士低声回应，我就是风暴</div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/wang-cheng/archives/">
        
          <span class="site-state-item-count">32</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/wang-cheng/tags/">
          
        <span class="site-state-item-count">12</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>



      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">王诚</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io/" class="theme-link" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.org/" class="theme-link" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
  </div>

        
<div class="busuanzi-count">
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    <span class="post-meta-item" id="busuanzi_container_site_uv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-user"></i>
      </span>
      <span class="site-uv" title="总访客量">
        <span id="busuanzi_value_site_uv"></span>
      </span>
    </span>
    <span class="post-meta-divider">|</span>
    <span class="post-meta-item" id="busuanzi_container_site_pv" style="display: none;">
      <span class="post-meta-item-icon">
        <i class="fa fa-eye"></i>
      </span>
      <span class="site-pv" title="总访问量">
        <span id="busuanzi_value_site_pv"></span>
      </span>
    </span>
</div>








      </div>
    </footer>
  </div>

  
  <script src="/wang-cheng/lib/anime.min.js"></script>
  <script src="/wang-cheng/lib/velocity/velocity.min.js"></script>
  <script src="/wang-cheng/lib/velocity/velocity.ui.min.js"></script>

<script src="/wang-cheng/js/utils.js"></script>

<script src="/wang-cheng/js/motion.js"></script>


<script src="/wang-cheng/js/schemes/pisces.js"></script>


<script src="/wang-cheng/js/next-boot.js"></script>




  















  

  

  

</body>
</html>
